package com.zhengb.algorithmdemo.basic.linklist;

/**
 * 单向链表基本操作
 *
 * @author zhengbo
 * @date 2020/2/15
 */
public class SingleDirectionLinkList {

    /**
     * 链表节点
     */
    private static class ListNode {

        private int data;

        private ListNode nextNode;

        public ListNode(int data) {
            this.data = data;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public ListNode getNextNode() {
            return nextNode;
        }

        public void setNextNode(ListNode nextNode) {
            this.nextNode = nextNode;
        }
    }

    public static void printList(ListNode headNode) {

        if (headNode.getNextNode() == null) {
            System.out.println(headNode.getData());
        }

        ListNode curNode = headNode;

        while (curNode != null) {
            System.out.println(curNode.getData());
            curNode = curNode.getNextNode();
        }
    }

    public static int listLength(ListNode headNode) {

        int length = 1;

        ListNode curNode = headNode;

        if (curNode.getNextNode() == null) {
            return length;
        }

        while ((curNode = curNode.getNextNode()) != null) {
            length++;
        }

        return length;
    }

    /**
     * 插入节点  时间负责读O(N)最差的情况在队尾插入 空间复杂度为O(1) 仅创建一个临时变量
     *
     * @param insertNode
     * @param headNode
     * @param position
     * @return
     */
    public static ListNode insertNode(ListNode insertNode, ListNode headNode, int position) {
        //链表为空 插入节点为头结点
        if (headNode == null) {
            return insertNode;
        }

        int listLength = listLength(headNode);
        //插入位置校验
        if (position > listLength + 1 || position < 1) {
            throw new IllegalArgumentException("insert position is not illegal");
        }

        //链表头插入
        if (position == 1) {
            insertNode.setNextNode(headNode);
            return insertNode;
        }

        ListNode preNode = headNode;
        int count = 1;
        //寻找插入位置的上一个节点
        while (count < position - 1) {
            preNode = preNode.getNextNode();
            count++;
        }
        //链表中间插入
        ListNode nextNode = preNode.getNextNode();
        preNode.setNextNode(insertNode);
        insertNode.setNextNode(nextNode);

        return insertNode;
    }

    /**
     * 删除链表节点 时间复杂度O(N)
     *
     * @param headNode
     * @param position
     * @return
     */
    public static ListNode deleteFromListNode(ListNode headNode, int position) {

        if (headNode == null) {
            return null;
        }

        int listLength = listLength(headNode);

        if (position > listLength || position < 1) {
            throw new IllegalArgumentException("delete position is not illegal");
        }
        //删除头结点
        if (position == 1) {
            ListNode secondNode = headNode.getNextNode();

            headNode.setNextNode(null);
            headNode = null;
            return secondNode;
        } else {

            ListNode preNode = headNode;

            int count = 1;
            //找到删除节点的前节点
            while (count < position) {
                preNode = preNode.getNextNode();
                count++;
            }
            //当前需要删除的节点
            ListNode deleteNode = preNode.getNextNode();
            //删除节点的前节点的next节点指向删除节点的下一个节点
            preNode.setNextNode(deleteNode.getNextNode());
            deleteNode = null;

            return headNode;
        }

    }

    public static void main(String[] args) {

        ListNode firstNode = new ListNode(1);
        ListNode secondNode = new ListNode(2);
        ListNode thirdNode = new ListNode(3);
        ListNode fourthNode = new ListNode(4);

        firstNode.setNextNode(secondNode);
        secondNode.setNextNode(thirdNode);
        thirdNode.setNextNode(fourthNode);
        fourthNode.setNextNode(null);

        System.out.println("链表长度:" + listLength(firstNode));

        printList(firstNode);

        ListNode insertNode = new ListNode(10);

        System.out.println("插入节点....");
        insertNode(insertNode, firstNode, 2);
        printList(firstNode);

        System.out.println("删除节点....");
        deleteFromListNode(firstNode, 4);
        printList(firstNode);
    }

}
